#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>

class Solution
{
public:
    long long maxRunTime(int n, std::vector<int>& batteries)
    {
        int len = batteries.size();
        long long sum = 0;
        int max = 0;
        for (int i = 0; i < len; i++)
        {
            sum += batteries[i];
            max = std::max(batteries[i], max);
        }
        if (len<n) return 0;
        if (sum / n > max)
        {
            return sum / n;
        }
        int l = 0;
        int r = max;
        int ans = 0;
        while (l <= r)
        {
            int m = l + ((r-l) >>1 );
            if (f(batteries,n,m,sum))
            {
                ans = m;
                l=m+1;
            }else
            {
                r = m-1;
               
            }
        }
        return ans;
    }
    bool f(std::vector<int>& batteries,int n,int limit,long long  sum)
    {
        int len = batteries.size();
        for (int i = 0; i < len; i++)
        {
            if (n>0&&batteries[i] > limit)
            {
                n--;
                sum-=batteries[i];
            }
            if (n==0) return true;
        }
        long long ans = n;
        
         return sum>=ans*limit;
        
    }
};

